1. Field of the Invention
The present invention relates to a modeling technique for three-dimensional (3D) free-form objects and an apparatus thereof, or more in particular to a method of realizing a solid modeler capable of modeling a three-dimensional object composed of free-form curved surfaces with a sensation as flexible as clay in generating three-dimensional object data for the three-dimensional computer graphics used for industrial or artistic designs and movie and television applications.
2. Description of the Related Art
With the progress of the graphics workstations, the 3D computer graphics technique has come to be widely used in various fields of industry and art. Especially, in recent years, the modeling of three-dimensional objects using free-form curved surfaces is increasingly required.
As such a technique, a method of generating free-form curved surfaces has been eagerly investigated in the field of CAD (Computer Aided Design), for which free-form curved surfaces have actually been widely used. The free-form curved surface used for CAD, however, is a two-dimensional open curved surface in most cases, and there has been no conventional method of effectively modeling closed curved surfaces, i.e., three-dimensional objects having free-form curved surfaces.
Especially, it has so far been very difficult to form a hole in or attach a handle to an existing 3D object or otherwise modify the geometric topology while retaining the smoothness of the shape of such an object.
In view of this, a modeling technique has been suggested in which a smooth density function F(x,y,z) is defined in three-dimensional space x-y-z while at the same time the representation by implicit functions is employed for defining the inside, the surface and the outside of object in the following manner. (J. F. Blimm, ACM Transaction on Graphics, 1(3), pp. 235-256, 1982; H. Nishimura et al., Trans. IEICE Japan, J68-D(4), pp. 718-725, 1985; G. Wyvill et al., The Visual Computer, 2(4), pp. 227-234, 1986)
Inside of object: Region satisfying F(x,y,z)&gt;0.5 PA1 Surface of object: Region satisfying F(x,y,z)=0.5 PA1 Outside of object: Region satisfying F(x,y,z)&lt;0.5 PA1 defining density distribution F(x,y,z) in a 3D space x-y-z; PA1 determining a scalar quantity a; PA1 defining a set of points (x,y,z) satisfying relation F(x,y,z)=a as a surface of object; PA1 defining a set of points (x,y,z) satisfying relation F(x,y,z)&gt;a as an inside of object; PA1 defining a set of points (x,y,z) satisfying relation F(x,y,z)&lt;a as an outside of object; PA1 producing density distribution c(x,y,z) by arranging a field-generating primitive prepared by a system or a user in a desired orientation and at a desired position; PA1 generating density distribution Gq (x,y,z) by blending the produced density distribution c (x,y,z) with density distribution Fq(x,y,z) (q=1, 2, . . . . . , n) already existing in the space, using a smooth function .PSI.(.xi., .zeta.) having two variables .xi., .zeta. in the manner as shown by equation Gq (x,y,z)=.PSI.(Fq (x,y,z), c (x,y,z)); PA1 sampling up to the mth-order partial derivative of the generated density distribution Gq (x,y,z) with respect to points included in a set .XI.q having a finite number of points in the 3D space, thereby determining sampling data .LAMBDA..sub.q (where the sampling data .LAMBDA..sub.q ={.mu..sub.p (i,j k)={1/(i!j!k!)}.differential..sup.i+j+k.sub.G.sbsb.q (x.sub.p, y.sub.p, z.sub.p)/.differential.x.sup.i .differential.y.sup.j .differential.z.sup.k .vertline.i+j+k=0, 1, . . . , m, i.gtoreq.0, j.gtoreq.0, k.gtoreq.0; all the points P=(x.sub.p, y.sub.p, z.sub.p) included in .XI.q}) and PA1 generating a smooth density distribution function Fq(x,y,z) for interpolating the determined sampling data .LAMBDA.q and expressing new density distribution Fq(x,y,z) with the generated function thereby to update the density distribution Fq(x,y,z); PA1 wherein density distribution F(x,y,z) obtained by convex combination of a number n of smooth functions Fq(x,y,z) (q=1, 2, . . . . , n) at each coordinate point is assumed to be density distribution F(x,y,z) representing an object. That is to say, the density distribution F(x,y,z) is expressed by the following equation: ##EQU1## where a function .lambda.q(x,y,z) (q=1, 2, . . . . . , n) is a smooth non-negative function and satisfies the following equation: ##EQU2## PA1 determining the scalar quantity a as a value satisfying the relation a&gt;0; and PA1 determining the density distribution c(x,y,z) of the field-generating primitive from equation c(x,y,z)=.phi.(f(x,y,z)-b+a) using a smooth function f(x,y,z) and a smooth monotone increasing function .phi.(.xi.) satisfying equations 0.ltoreq..phi.(.xi.).gtoreq.2a and .phi.(a)=a, the function f(x,y,z) being used for defining a set of points (x,y,z) satisfying the relation f(x,y,z)=b as the surface of object, defining a set of points (x,y,z) satisfying relation f(x,y,z)&gt;b as the inside of the object, and defining a set of points (x,y,z) satisfying the relation f(x,y,z)&lt;b as the outside of object, with regard to a scalar quantity b. PA1 determining the scalar quantity a as a value satisfying relation a&gt;0; PA1 defining the function c(x,y,z) as follows using a function d associated with a smooth bijection (one-to-one onto-mapping) d: R.sub.1 .fwdarw.R.sub.2 from region R.sub.1 to region R.sub.2 in the 3D space and smooth inverse mapping d.sup.-1. R.sub.2 .fwdarw.R.sub.1 PA1 c(x,y,z)=F(d.sup.-1 (x,y,z)) PA1 (point (x,y,z) included in the region R.sub.2) PA1 c(x,y,z))=0 PA1 (point (x,y,z) not included in the region R.sub.2) PA1 regarding the defined function c(x,y,z) as the density distribution of the field-generating primitive; PA1 updating the density distribution Fq(x,y,z) according to equation Fq(x,y,z)-{Fq(x,y,z).multidot.D(x,y,z)/(2a)} using density distribution D(x,y,z) of the field-generating primitive approximating the region R.sub.1 in surface shape; and PA1 blending the updated density distribution Fq(x,y,z) and the field-generating primitive c(x,y,z) according to the following equation, thereby generating density distribution Gq(x,y,z) and realizing a deformation of the object: EQU Gq(x,y,z)=Fq(x,y,z)+c(x,y,z)-{Fq(x,y,z).multidot.c(x,y,z)/(2a)}. PA1 defining density distribution F(x,y,z) in a 3D space x-y-z; PA1 determining a scalar quantity a; PA1 defining a set of points (x,y,z) satisfying relation F(x,y,z)=a as a surface of object; PA1 defining a set of points (x,y,z) satisfying relation F(x,y,z)&gt;a as an inside of object; PA1 defining a set of points (x,y,z) satisfying relation F(x,y,z)&lt;a as an outside of object; PA1 arranging a field-generating primitive prepared by a system or a user in a desired orientation and at a desired position thereby to produce density distribution c(x,y,z); PA1 blending the produced density distribution c(x,y,z) with density distribution Fq(x,y,z)(q=1, 2, . . . . n) already existing in the space thereby to generate density distribution Gq(x,y,z); PA1 sampling up to the mth-order partial derivatives of the generated density distribution Gq(x,y,z) with respect to points included in a set .XI.q having a finite number of points in the 3D space thereby to determine sampling data .LAMBDA.q; PA1 generating a smooth density distribution function Fq(x,y,z) for interpolating the determined sampling data .LAMBDA.q and expressing new density distribution Fq(x,y,z) with the generated function thereby to update the density distribution Fq(x,y,z); and PA1 assuming density distribution F(x,y,z) obtained by convex combination of a number n of smooth density distribution functions Fq(x,y,z)(q=1, 2, . . , n) at each coordinate point as density distribution F(x,y,z) representing an object. PA1 defining density distribution F(x,y,z) in a 3D space; PA1 determining a scalar quantity a; PA1 defining a set of points (x,y,z) satisfying relation F(x,y,z)=a as a surface of object; PA1 defining a set of points (x,y,z) satisfying relation F(x,y,z)&gt;a as an inside of object; PA1 defining a set of points (x,y,z) satisfying relation F(x,y,z)&lt;a as an outside of object; PA1 arranging a field-generating primitive prepared by a system or a user in a desired orientation and at a desired position thereby to produce density distribution c(x,y,z); PA1 blending the produced density distribution c(x,y,z) with density distribution Fq(x,y,z) (q=1, 2, . . . , n) already existing in the space using a smooth function .PSI.(.xi., .zeta.) having two variables .xi., .zeta. according to equation Gq(x,y,z)=.PSI.(Fq(x,y,z), c(x,y,z)) thereby to generate density distribution Gq(x,y,z); PA1 sampling up to the mth-order partial derivatives of the generated density distribution Gq(x,y,z) at points included in a set .XI.q having a finite number of points in the 3D space thereby to determine sampling data .LAMBDA.q; PA1 generating smooth density distribution function Fq(x,y,z) for interpolating the determined sampling data .LAMBDA.q and expressing new density distribution Fq(x,y,z) with the generated function, thereby updating the density distribution Fq(x,y,z); and PA1 assuming that density distribution F(x,y,z) obtained by convex combination of a number n of smooth distribution functions Fq(x,y,z) (q=1, 2, . . . , n) at each coordinate point as density distribution F(x,y,z) representing an object. PA1 producing means for arranging a field generating primitive prepared by a system or a user in a desired orientation and at a desired position thereby to produce density distribution c(x,y,z); PA1 generating means for blending the produced density distribution c(x,y,z) with density distribution Fq(x,y,z) (q=1, 2, . . . . , n) already existing in the space using a smooth function .PSI.(.xi., .zeta.) having two variables .xi., .zeta. in accordance with equation Gq(x,y,z)=.PSI.(Fq(x,y,z), c(x,y,z)) thereby to generate density distribution Gq(x,y,z); PA1 sampling data computing means for sampling up to the m-order partial derivatives of the generated density distribution Gq(x,y,z) at points included in a set .XI.q having a finite number of points in the 3D space, thereby determining sampling data ##EQU3## PA1 updating means for generating a smooth density distribution function Fq(x,y,z) for interpolating the determined sampling data .LAMBDA.q and expressing new density distribution Fq(x,y,z) with the generated function, thereby to update the density distribution Fq(x,y,z), and assuming that density distribution obtained by the convex combination of a number n of smooth functions F(x,y,z) (q=1, 2, . . . . , n) at each coordinate point as density distribution F(x,y,z) representing an object. PA1 producing means for arranging a field generating primitive prepared by a system or a user in a desired orientation and at a desired position thereby to generate density distribution c(x,y,z); PA1 generating means for blending the produced density distribution c(x,y,z) with density distribution Fq(x,y,z) (q=1, 2, . . . . , n) already existing in the space thereby to generate density distribution Gq(x,y,z); PA1 sampling data computing means for sampling up to the m-order partial derivatives of the generated density distribution Gq(x,y,z) at points included in a set .XI.q having a finite number of points in the 3D space thereby to determine sampling data .LAMBDA.q; and PA1 updating means for generating a smooth function Fq(x,y,z) for interpolating the determined sampling data .LAMBDA.q, expressing new density distribution Fq(x,y,z) with the generated function thereby to update the density distribution Fq(x,y,z) assuming that the density distribution obtained by the convex combination of a number n of smooth density distribution functions Fq(x,y,z) (q=1, 2, . . . , n) at each coordinate point as density distribution F(x,y,z) representing an object. PA1 c(x,y,z)=F(d.sup.-1 (x,y,z)) (point (x,y,z) included in the region R.sub.2) PA1 c(x,y,z)=0(point (x,y,z) not included in the region R.sub.2) PA1 .PSI..sub.- (Fq(x,y,z), D(x,y,z)).
The aforementioned modeling technique is typically represented by a method in which the density distribution is corrected smoothly in the manner described below. Several field-generating primitives, each of which has a smooth density distribution and is usable by the user, are prepared. The user arranges these field-generating primitives while adjusting the sign and gradient of the density and the size at an arbitrary spatial position with an arbitrary orientation. The density distribution of these field-generating primitives is added to the density distribution already existing in the space.
As shown in FIG. 1A, for example, in the case where it is desired to form a through hole at the center of an ellipsoid A expressed by Equation 1.1, an ellipsoid primitive B having a negative density given by Equation 1.2 is arranged at the center of the ellipsoid A to generate a new density distribution F(x,y,z) expressed by Equation 1.3. Thus an ellipsoid A-B having a through hole formed therein is obtained as shown in FIG. 1B. EQU C.sub.A (x,y,z)=0.5.multidot.exp[1-(x.sup.2 +y.sup.2 +4z.sup.2)](1.1) EQU C.sub.B (x,y,z)=-0.5.multidot.exp[1-(4x.sup.2 +4y.sup.2 +(0.5z).sup.2)](1.2) EQU F(x,y,z)=C.sub.A (x,y,z)+C.sub.B (x,y,z) (1.3)
Except for the points with a gradient vector of zero for density function, an isosurface having the density of 0.5 automatically generates a smooth surface. According to this method, the object A-B with the through hole different in topology from the original ellipsoid is readily modeled.
In the above-mentioned modeling technique using the implicit function, however, the use of simple density addition is often accompanied by the fact that a positive or negative density distribution with a large absolute value is exhibited for other than visual surfaces (object surfaces) with the density of 0.5. In the case where a new object is modeled in such a spatial region, a shape not intended by the designer may undesirably be generated.
In the case shown above, for example, the density value F(0, 0, 0.7) at a point (0, 0, 0.7) in proximity to the through hole of the ellipsoid A-B is -1.010 . . . Therefore, an attempt to place an ellipsoid C represented by Equation 1.4 at the center of the through hole as shown in FIG. 1C results in F(0, 0, 0.7)+Cc(0, 0, 0.7)=0.307 . . . .&lt;0.5 since Cc(0, 0, 0.7)=1.318 . . . . EQU C.sub.C (x,y,z)=0.5.multidot.exp[1-(16x.sup.2 +16y.sup.2 +(0.25z).sup.2)](1.4)
The point (0, 0, 0.7) is the outside of object, and therefore the ellipsoid C is fragmented into three portions as shown in FIG. 1D against the will of the designer. As a consequence, the designer is required to proceed with the modeling work by awkward means while always monitoring the behavior of density distribution in the space in addition to the shape (that is the visual surface) of the object.
Also, in the case where it is desired to twist, bend or otherwise deform an object having density distribution composed of a plurality of field-generating primitives, the density distribution after deformation is greatly complicated. The conventional modeling technique using the implicit function representation is intended only for the density distribution capable of being expressed by a combination of addition and subtraction of limited types of field-generating primitives. Thus the problem is how to combine the usable field-generating primitives to express the density distribution after deformation.
Consider the simplest case in which a peanut-like shape is generated by bending a single ellipsoid primitive. How the addition and subtraction of a plurality of ellipsoid primitives are combined to represent the peanut-like shape is not a simple problem. The deforming operation for an object cannot be used in the course of modeling work according to the prior art.